Internet Info 1993

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / inet / ien / ien-109 < prev next >

Wrap

Text File | 1988-12-01 | 46.5 KB | 1,609 lines

HOW TO BUILD A GATEWAY Virginia Strazisar IEN #109 August 31, 1979 TABLE OF CONTENTS 1. Introduction...............................................1 2. Information Maintained by Gateways.........................1 3. Initialization.............................................3 4. Determining Connectivity to Networks.......................3 5. Determining Connectivity to Neighbors......................4 6. Exchanging Routing Information.............................4 7. Computing Routes...........................................5 8. Forwarding Traffic.........................................7 9. Non-Routing Gateways.......................................7 10. Adding New Neighbors and Networks..........................8 11. Communications with Hosts..................................9 12. Future Modifications......................................10 13. Packet Formats............................................11 14. Examples..................................................19 15. Tables and Variables......................................23 16. Events and Responses......................................25 1. Introduction This is a description of how to implement a gateway. The gateway forwards internet traffic formatted as described in IEN #111, "Internet Protocol". The gateway polls its attached networks and neighbor gateways to determine its connectivity to them, then exchanges this information with its neighbor gateways in order to compute routes to each network in the catenet. When gateways or network interfaces fail, the gateways compute alternate routes to the networks. The design for this gateway routing strategy was originally presented in IEN #30, "Gateway Routing, An Implementation Specification". That document gives an overview of the design and explains some of the decisions made in designing this routing strategy. Since IEN #30 was released, this routing strategy has been implemented in several gateways. During implementation, several modifications were made to the original design, thus, those sections of IEN #30 covering the detailed specification of the design are obsolete and are replaced by this document. 2. Information Maintained by Gateways Gateways must maintain information about their connectivity to networks and other gateways. The functional description below explains how this information is obtained and modified by the gateways. For the purpose of explaining the gateway functions, this information is organized into the following tables and variables. Number of Networks The number of networks for which the gateway maintains routing information and to which it can forward packets. The gateways maintain and exchange routing information indexed by network numbers. Thus, the Number of Networks also corresponds to the highest numbered network to which the gateway can route traffic. (Network numbers are listed in IEN #117, "Assigned Numbers".) Number of Neighbors The number of neighbor gateways with which the gateway exchanges routing information. A neighbor gateway of gateway X is any gateway that has an interface on the same network as gateway X. If gateway X and its neighbor have more than one network in common, then each neighbor gateway interface on a network to which gateway X is attached is considered to be a separate neighbor. - 1 - Gateway Addresses The address of the gateway on each network to which it is attached. Neighbor Addresses The addresses of the neighbor gateways. Connectivity to Neighbors A vector of the status of connectivity between the gateway and each of its neighbor gateways. The connectivity is determined by polling the neighbors. Routing Updates The routing updates that are sent to the neighbor gateways. Each routing update contains the distance from the gateway to each network. There is one routing update for each neighbor. Distance Matrix A matrix of the routing updates received from each of the neighbor gateways. Routing updates contain the distance from a gateway to each network. Minimum Distance Vector A vector of the minimum distance to each network. Distance is measured in networks traversed; a gateway which is physically attached to a network is zero hops from that network; if the gateway must send through one other gateway to get to a network, then it is one hop from that network. Routing updates from non-routing neighbor gateways A routing update for each neighbor gateway that does not participate in this routing scheme. This is the update that the gateway would receive from this neighbor if the neighbor did participate in routing. Routing Table A table containing, for each network, a list of the neighbor gateways on a minimum length route to that network. - 2 - Send Sequence Number The sequence number that the gateway will use to transmit the next routing update to its neighbors. Receive Sequence Numbers The sequence number that the gateway received in the last routing update from each of its neighbors. There is a sequence number for each neighbor. 3. Initialization The gateway is initialized with the following information: The gateway's address on each network to which it is attached. The addresses of its neighbors. A routing update from each of its neighbor gateways that do not participate in routing. Initially, the gateway should assume that all its neighbor gateways are down, that it is disconnected from networks to which it is attached, and that the distance reported in routing updates from each neighbor to each network is infinity (see "Computing Routes"). 4. Determining Connectivity to Networks The gateway must determine its connectivity to networks to which it is physically attached. The gateway is connected to a network if it can send and receive internet packets on its interface to that network. The method that the gateway uses to determine its connectivity to a network is network dependent. In some networks, the host to network protocol determines whether or not data packets can be sent and received on the host interface. In these networks, the gateway can simply check status information provided by the protocol in order to determine if it can communicate with the network. In other networks, where the host to network protocols are less complex, it may be necessary for the gateway to send traffic to itself to determine if it can communicate with the network. In these networks, the gateways can periodically poll the network to determine if the network interface is operational. For purposes of computing distances and routes to networks, if the gateway can send and receive traffic on its network interface, then its distance to the network is zero; if it cannot send and receive traffic on the interface, then its distance to - 3 - the network is infinity. Note that if a gateway's network interface is not working, it may still be able to send traffic to the network on an alternate route via one of its neighbor gateways. 5. Determining Connectivity to Neighbors A neighbor gateway is in one of three states: up, down, or recovering. In the latter case, the gateway has communicated with its neighbor, and is in a waiting period to determine whether it will be able to continue to communicate with the neighbor. This state exists to prevent a gateway from using a neighbor gateway to forward traffic when communications between it and the neighbor are extremely lossy. The gateway determines its connectivity to each neighbor gateway as follows. Initially, the neighbor is assumed to be "down". The gateway sends an echo packet (see "Packet Formats") to the neighbor gateway every N seconds and increments a count of echo packets outstanding to that neighbor. When the gateway receives an echo reply packet from the neighbor, it clears the count of outstanding echo packets. If that neighbor was "down", the gateway starts an X second timer and sets the neighbor's status to "recovering". If after X seconds, the neighbor's status is still "recovering", then the neighbor's status is changed to "up". If the count of echo packets outstanding to a neighbor is equal to Z, the neighbor's status is set to "down". As probes are sent every N seconds, a neighbor's status is changed to "down" if it does not respond within (N * Z) seconds. Note that the waiting period, X, during which the neighbor's status is "recovering" should be at least several times the interval (N * Z seconds) needed to declare the neighbor "down". This prevents the neighbor gateway from cycling rapidly between the "up" and "down" states. The gateway maintains a vector of the connectivity between it and its neighbors. This vector is used in computing distances and routes to networks. The vector contains K entries where K is the number of neighbors. If the state of the Jth neighbor is either "down" or "recovering", then the Jth entry of the vector is set to infinity; if the state of the Jth neighbor is "up" then the Jth entry of the vector is set to one. 6. Exchanging Routing Information The gateway receives and transmits routing information reliably using sequence numbered packets and a retransmission and acknowledgement scheme. This scheme works as follows. For each neighbor, the gateway remembers the Receive Sequence Number, R, that it received in the most recent routing packet from that neighbor. This value is initialized by setting it to the sequence number received in the first routing packet received - 4 - from a neighbor after that neighbor's status is set to "up". On receipt of a routing packet from a neighbor, the gateway subtracts the Receive Sequence Number, R, from the sequence number in the routing packet, S. If this value (S-R) is greater than or equal to zero, then the gateway accepts the routing packet, sends an acknowledgement to the neighbor containing the sequence number S, and replaces the Receive Sequence Number, R, with S. If this value (S-R) is less than zero, the gateway rejects the routing packet and sends a negative acknowledgement to the neighbor with sequence number R. The gateway has a Send Sequence Number, N, for sending routing packets to all of its neighbors. This sequence number can be initialized to any value. The Send Sequence Number is incremented each time a new routing update is created. On receiving an acknowledgement for a routing update, the gateway subtracts the sequence number acknowledged, A, from the Send Sequence Number, N. If the value (N-A) is non-zero, then an old routing update is being acknowledged. The gateway continues to retransmit the most recent routing update to the neighbor that sent the acknowledgement. If (N-A) is zero, the routing update has been acknowledged. Note that only the most recent routing update need be acknowledged; if a second routing update is generated before the first routing update is acknowledged, only the second routing update need be acknowledged. If a negative acknowledgement is received, the gateway subtracts the sequence number negatively acknowledged, A, from its Send Sequence Number, N. If this value (N-A) is less than zero, then the gateway replaces its Send Sequence Number, N, with the sequence number negatively acknowledged plus one, A+1, and retransmits the update to all its neighbors. If (N-A) is greater than or equal to zero, then the gateway continues to retransmit the routing update using sequence number N. In order to maintain the correct sequence numbers at all gateways, routing updates must be retransmitted to all neighbors if the Send Sequence Number changes, even if the routing information does not change. The gateway retransmits routing updates periodically until they are acknowledged and whenever its Send Sequence Number changes. The gateway sends routing updates only to neighbors that are in the "up" state, not to neighbors that are "down" or "recovering". Examples of the sequence number strategy are given below. 7. Computing Routes A routing update contains the number of networks that a gateway is reporting about followed by a list of the distances to these networks, indexed by network number. Assuming that the gateway has checked the sequence number of a routing update that it has - 5 - received and has decided to accept the update, the information in the update is processed as follows. The gateway contains a N x K distance matrix, where N is the number of networks and K is the number of neighbor gateways. An entry in this matrix, represented as d(I,J), is the distance to network I from neighbor J as reported in the most recent routing update from neighbor J. The gateway also contains a vector indicating the connectivity between itself and its neighbor gateways. The values in this vector are computed as discussed above (see "Determining Connectivity to Neighbors"). The value of the Jth entry of this vector, which is the connectivity between the gateway and the Jth neighbor, is represented as d(J). The gateway copies the routing update received from the Jth neighbor into the appropriate row of the distance matrix, then updates its routes as follows. The gateway calculates a minimum distance vector, containing the minimum distance to each network from the gateway. The Ith entry of this vector, represented as MinD(I) is: MinD(I) = minimum over all neighbors of d(J) + d(I,J) where d(J) is the distance between the gateway and the Jth neighbor and d(I,J) is the distance from the Jth neighbor to the Ith network. If the Ith network is attached to the gateway and the gateway can send and receive traffic on its network interface (see "Determining Connectivity to Networks"), then the gateway sets the Ith entry of the minimum distance vector to zero. Using the minimum distance vector, the gateway computes a list of neighbor gateways through which to send traffic to each network. The entry for network I contains all neighbors such that: MinD(I) = d(J) + d(I,J) In other words, the entry for network I contains all neighbors such that the distance from the gateway to the neighbor plus the distance from the neighbor to the network is equal to the minimum distance from the gateway to the network. After updating its routes to the networks, the gateway computes the new routing updates to be sent to its neighbors as follows. For each neighbor, J, the gateway constructs a routing update which is a N entry vector where N is the number of networks. The Jth entry of this vector is: MinD(I) if MinD(I) less than or equal to d(I,J) infinity if MinD(I) greater than d(I,J) - 6 - where d(I,J) is the distance from the Jth neighbor to the Ith network and MinD(I) is the minimum distance from the gateway to the Ith network. In other words, the gateway reports its distance to a network to a neighbor only if it is as close to or closer to a network than its neighbor. Finally, the gateway must determine whether it should send routing updates to its neighbors. The gateway maintains a copy of the most recent routing updates that it sent to each of its neighbors. The gateway computes the new routing updates to send to each of its neighbors. If any of these routing updates are different than the preceding updates, then the gateway sends new routing updates to its neighbors. If no routing information has changed since the last routing update was sent, then the gateway does not need to send new routing updates. The gateway sends routing updates only to neighbors that are currently in the "up" state. The gateway requests routing updates from neighbors that are in the "up" state, but have not yet sent a routing update to it. Routing updates are requested by setting the appropriate bit in the routing update being sent (see "Packet Formats"). Similarly, if a gateway receives a routing update from a neighbor in which the bit requesting a routing update is set, the gateway sends the neighbor the most recent routing update. 8. Forwarding Traffic On receipt of a packet to be forwarded, the gateway extracts the internet destination network field from the packet. If the gateway is attached to the network, and its network interface is operational, then the gateway simply composes the appropriate local network header for the destination network and sends the packet. If the gateway is not connected to the network, then the gateway checks the list of the neighbors on the route to the destination network. If there are no neighbors on the list, then the gateway drops the packet and sends the internet source a "destination unreachable" message (see "Communications with Hosts"). If there are one or more neighbors on a route to the destination network, then the gateway sends the packet to one of these neighbors. If there is more than one neighbor, then the neighbors are used in a round robin fashion. 9. Non-Routing Gateways Non-routing gateways are gateways that forward internet traffic, but that do not participate in this routing scheme. Whenever - 7 - possible, traffic is forwarded only through gateways that participate in this routing scheme. Non-routing gateways are used to forward traffic only if they provide the only route to a network. These gateways are used as follows. Consider a gateway, G1. The only non-routing gateways that it needs to know about are its neighbor gateways, as these are the gateways from which it would normally receive routing updates. For each non-routing neighbor gateway of gateway G1, compute the routing update that would be sent to G1 assuming that all gateways and network connections are operational. These routing updates are assembled in G1. The gateway, G1, first computes its minimum distance vector as explained above, using only the routing updates from neighbors that participate in routing. If the minimum distance to any network is infinity, i.e. the network is unreachable via any of the routing gateways, then the minimum distance to that network is re-computed using the routing update compiled for the non-routing neighbor gateway. For purposes of computing the minimum distance to a network, the gateway, G1, assumes that the distance between itself and the neighbor gateway is zero. After computing the minimum distance vector, the gateway compiles the list of neighbor gateways through which to send traffic to each network and sends routing updates to its neighbors as explained above (see "Computing Routes"). The gateway does not send routing updates to the non-routing neighbor gateways. 10. Adding New Neighbors and Networks Gateways dynamically add routing information about new neighbors and new networks to their tables. The gateway maintains a list of neighbor gateway addresses. When a routing update is received, the gateway searches this list of addresses for the internet source address of the routing update packet. If the internet source address of the routing update is not contained in the list of neighbor addresses, the gateway adds this address to the list of neighbor addresses. The gateway accepts the routing update, sets the neighbor's connectivity status to "up", and computes new routes as explained above. The gateway also begins polling this new neighbor to monitor its connectivity. Note that this strategy requires that one gateway in each pair of neighbor gateways must have the neighbor's address assembled in its tables. The newest gateway can be given a complete list of neighbors, thus avoiding the need to re-assemble older gateways when new gateways are installed. Gateways obtain routing information about new networks as follows. The gateway maintains a count of the number of networks for which it currently contains routing information, N. When a routing update is received, the gateway compares this number to the number of networks reported in the routing update, M. If M - 8 - is greater than N, then the gateway updates the count of networks for which it maintains routing information to include the new networks. Next, the gateway expands its distance matrix to include the number of networks reported. The distance matrix is the matrix of distances to networks as reported in routing updates from the neighbor gateways. In expanding the matrix, the gateway assumes the distance to all new networks is infinity. After expanding the matrix, the gateway computes new routes and new routing updates as outlined above. Note that expanding neighbor address tables and distance matrices may present an implementation problem. In practice, these tables can be assembled to contain some maximum number of neighbors and networks. If a new neighbor cannot be added to a gateway's tables, then routing updates or echo packets from that neighbor should be ignored. The new neighbor will assume that the gateway is down and will not use it to forward traffic. If a gateway cannot add a new network to its routing tables, it can still accept routing updates containing information about the new network, but it will be unable to route traffic to the new network. The routing updates that it sends to its neighbors will not contain information about the new network. Whenever a gateway receives a routing update that does not report the distance to a network, the gateway should assume that the distance is infinity. 11. Communications with Hosts The gateway sends messages to internet hosts in several situations: when the gateway cannot reach the internet destination, when the gateway does not have the buffering capacity to forward a packet, and when the gateway can direct the host to send traffic on a shorter route. These situations are explained in more detail below. The formats for messages sent from a gateway to a host are given in the section "Packet Formats". If, according to the information in the gateway's routing tables, the network specified in the internet destination field of a packet is unreachable, i.e. the distance to the network is infinity, the gateway sends a destination unreachable message to the internet source host of the packet. In addition, in some networks, the gateway may be able to determine if the internet destination host is unreachable. Gateways in these networks may send destination unreachable messages to the source host when the destination host is unreachable. The gateway may discard internet packets if it does not have the buffer space needed to queue the packets for output to the next network on the route to the destination network. If the gateway - 9 - discards a packet, it sends a source quench message to the internet source host of the packet. The source quench message is a request to the host to cut back the rate at which it is sending traffic to the internet destination. The gateway sends a source quench message for every message that it discards. On receipt of a source quench message, hosts should cut back the rate at which they are sending traffic to the specified destination until they no longer receive source quench messages from the gateway. The hosts can then gradually increase the rate at which they are sending traffic to the destination until they again receive source quench messages from the gateway. The gateway sends a redirect message to a host in the following situation. A gateway, G1, receives an internet packet from a host on a network to which the gateway is attached. The gateway, G1, checks its routing table and obtains the address of the next gateway, G2, on the route to the packet's internet destination network, X. If G2 and the host identified by the internet source address of the packet are on the same network, a redirect message is sent to the host. The redirect message advises the host to send its traffic for network X directly to gateway G2 as this is a shorter path to the destination. The gateway forwards the original data packet to its internet destination. 12. Future Modifications As there are now many networks planned or implemented, and as these networks may be assigned a wide range of network numbers, it is no longer feasible to maintain routing information in tables indexed by network numbers. Gateways will be modified to use a hash table scheme to convert network numbers to internal indices to reference routing tables. The information in routing updates exchanged by the gateways will no longer be indexed by network number. The format of routing updates will be modified to include both the network number and the distance to the network. These modifications will be documented in a separate note. - 10 - 13. Packet Formats Gateway to gateway and gateway to host communications use the version 4 internet protocol. The first octet of the data portion of the packet is a gateway type field; the value of this field determines the format of the remaining data. The format of internet packets is explained in IEN #111, "Internet Protocol". Unless otherwise noted under the individual format descriptions, the values of the internet header fields are as follows: Version 4 IHL Internet header length in 32-bit words; this is 5. Type of Service 0 Total Length Length of internet header and data in octets. Identification, Flags, Fragment Offset Used in fragmentation, see IEN #111. Time to Live Time to live in seconds; as this field is decremented at each machine in which the packet is processed, the value in this field should be at least as great as the number of gateways which this packet will traverse. (This must be considered in the messages sent to hosts.) Protocol 3 Header Checksum The 16 bit one's complement of the one's complement sum of all 16 bit words in the header. For computing the checksum, the checksum field should be zero. This checksum may be replaced in the future, see updates of the Internet Protocol Specification. Source Address The address of the gateway that composes the packet. Unless otherwise noted, this can be any of the gateway's addresses. Destination Address The address of the gateway or host to which the packet should be sent. - 11 - Routing Update 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! unused ! Sequence Number ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! NU ! N ! Distance 1 ! Distance 2 ! Distance 3 ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Distance N-3 ! Distance N-2 ! Distance N-1 ! Distance N ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Gateway Type 1 Sequence Number The 16-bit sequence number used to transmit routing updates. NU A 1-bit field. This bit is set if the source gateway requests a routing update from the destination gateway. N The number of networks for which distances are reported in this update. Distance 1..N A set of octets that are the values in the routing update for distances to network numbers 1 through N. The network numbers are listed in IEN #117, "Assigned Numbers". If the Ith network is unreachable, the distance to the network is infinity, which is represented as 177 (octal). - 12 - Acknowledgement or Negative Acknowledgement 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! unused ! Sequence Number ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Gateway Type 2 for acknowledgement; 10 (decimal) for negative acknowledgement. Sequence Number The 16-bit sequence number that the gateway is acknowledging or negatively acknowledging. - 13 - Destination Unreachable Packet 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! Code ! unused ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Internet Header + 64 bits of Original Data Packet ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Destination Address The source network and address from the original data packet. Gateway Type 3 Code 0 = net unreachable; 1 = host unreachable. Internet Header + 64 bits of Data Packet The internet header plus the first 64 bits of the original data packet. This data is used by the host to match the message from the gateway to the appropriate process. If a higher level protocol uses port numbers, they are assumed to be in the first 64 data bits of the original data packet. - 14 - Source Quench Packet 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! unused ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Internet Header + 64 bits of Original Data Packet ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Destination Address The source network and address of the original data packet. Gateway Type 4 Internet Header + 64 bits of Data Packet The internet header plus the first 64 bits of the original data packet. This data is used by the host to match the message from the gateway to the appropriate process. If a higher level protocol uses port numbers, they are assumed to be in the first 64 data bits of the original data packet. - 15 - Redirect Packet 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! unused ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ !Gateway Network! Gateway Address ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Internet Header + 64 bits of Original Data Packet ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Destination Address The source network and address of the original data packet. Gateway Type 5 Gateway Network Address of the gateway to which traffic Gateway Address for the network specified in the internet destination network field of the data packet should be sent. Internet Header + 64 bits of Data Packet The internet header plus the first 64 bits of the original data packet. This data is used by the host to match the message from the gateway to the appropriate process. If a higher level protocol uses port numbers, they are assumed to be in the first 64 data bits of the original data packet. - 16 - Echo or Echo Reply Packet 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! unused ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Source Address In an echo packet, the address of the gateway on the same network as the neighbor to which it is sending the echo packet. In an echo reply packet, the source and destination addresses are simply reversed. Gateway Type 8 for echo packet; 0 for echo reply. - 17 - Net Interface Status Packet 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Gateway Type ! unused ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Source Address Destination Address The address of the gateway's network interface. The gateway can send Net Interface Status Packets to itself to determine if it is able to send and receive traffic on its network interface. Gateway Type 9 - 18 - 14. Examples The following examples illustrate the sequence number scheme used for sending and receiving routing updates. Example 1: Gateway G has three neighbors: A, B and C. Gateway G's Send Sequence Number is 5. Connectivity between gateway G and gateway A was broken and is now restored; thus, A has not received the last update from G. Gateway A's Receive Sequence Number for G is 3. Gateway B's Receive Sequence Number for G is 4. Gateway C's Receive Sequence Number for G is 4. Initially, gateway G has the following values in its tables: Send Sequence Received Acknowledgement from Neighbors A B C 5 N N N (N for no, Y for yes) G (5) ---> A G sends routing update 5 to its neighbors G (5) ---> B G (5) ---> C A (ACK 5) ---> G A computes (sequence number received in packet - Receive Sequence Number) = (5-3); as this is greater than or equal to zero, A acknowledges routing update 5 and replaces Receive Sequence Number for G with 5 B (ACK 5) ---> G B computes (sequence number received in packet - Receive Sequence Number) = (5-4); as this is greater than or equal to zero, B acknowledges routing update 5 and replaces its Receive Sequence Number for G with 5 C (ACK 5) ---> G On receipt of these acknowledgements, G computes (Send Sequence Number - sequence number acknowledged) = (5-5). As this value is zero, G notes that each of its neighbors has acknowledged its routing update. - 19 - Gateway G now has the following values in its tables: Send Sequence Received Acknowledgement from Neighbors A B C 5 Y Y Y Gateway A's Receive Sequence Number for G is 5. Gateway B's Receive Sequence Number for G is 5. Gateway C's Receive Sequence Number for G is 5. - 20 - Example 2: Gateway G has three neighbors: A, B, and C. Gateway G's Send Sequence Number is 24. Gateway A has been disconnected from gateway G for some long time, thus, it has missed many updates from G and G's Send Sequence Number has now wrapped around. Gateway A's Receive Sequence Number for G is 500. Gateway B's Receive Sequence Number for G is 23. Gateway C's Receive Sequence Number for G is 23. Initially, gateway G has the following values in its tables: Send Sequence Received Acknowledgement from Neighbors A B C 24 N N N (N for no, Y for yes) G (24) ---> A G sends routing update 24 to all its neighbors G (24) ---> B G (24) ---> C A (NAK 500) ---> G A computes (sequence number received in packet - Receive Sequence Number) = (24-500); as this is less than zero, A sends a negative acknowledgement with sequence number 500 On receipt of the negative acknowledgement, gateway G computes (Send Sequence Number - sequence number negatively acknowledged) = (24-500). As this value is less than zero, G replaces its Send Sequence Number with 501 and retransmits the routing update with this sequence number. G (501) ---> A G (501) ---> B G (501) ---> C A (ACK 501) ---> G A computes (sequence number received in packet - Receive Sequence Number) = (501-500); as this is greater than or equal to zero, A acknowledges sequence number 501 and replaces its Receive Sequence Number for G with 501 B (ACK 24) ---> G B receives the update from G with sequence number 24; B computes (sequence number received in packet - Receive Sequence Number) = (24-23); as this is greater than or equal to zero, B acknowledges sequence number 24 and replaces its Receive Sequence Number for G with 24 C (ACK 24) ---> G - 21 - On receipt of these acknowledgements, G computes (Send Sequence Number - sequence number acknowledged) = (501-24). As this value is non-zero, G retransmits the routing update to these neighbors. G (501) ---> B G (501) ---> C B (ACK 501) ---> G B computes (sequence number received in packet - Receive Sequence Number) = (501-24); as this is greater than or equal to zero, B acknowledges sequence number 501 and replaces its Receive Sequence Number for G with 501 C (ACK 501) ---> G On receipt of these acknowledgements, G computes (Send Sequence Number - sequence number acknowledged) = (501-501). As this value is zero, G notes that each of its neighbors has acknowledged its routing update. Gateway G now has the following values in its tables: Send Sequence Received Acknowledgement from Neighbors A B C 501 Y Y Y Gateway A's Receive Sequence Number for G is 501. Gateway B's Receive Sequence Number for G is 501. Gateway C's Receive Sequence Number for G is 501. - 22 - 15. Tables and Variables The following is a list of variables and tables in a typical gateway implementation. 1. Number of Networks 2. Number of Neighbors 3. Gateway Addresses The addresses of the gateway's network interfaces. 4. Neighbor Gateway Addresses The address of each gateway network interface that is on the same network as this gateway. 5. Neighbor Connectivity Vector A vector of the connectivity between this gateway and each of its neighbors. It contains K entries where K is the Number of Neighbors. Values in this vector are computed as explained in "Determining Connectivity to Neighbors". 6. Distance Matrix A matrix of the routing updates received from the neighbor gateways. 7. Minimum Distance Vector A vector containing the minimum distance to each network. It is computed as described in "Computing Routes". 8. Routing Updates A set of vectors giving the distance from this gateway to each network. There is a separate vector to be sent to each neighbor. These are computed as described in "Computing Routes". 9. Routing Updates from Non-Routing Gateways The routing updates that would have been received from each neighbor gateway that does not participate in this routing strategy. These are computed as described in "Non-Routing Gateways". - 23 - 10. Routing Table A table containing, for each network, a list of the neighbor gateways on a minimum distance route to the network. This is computed as described in "Computing Routes". 11. Send Sequence Number The sequence number that will be used to send the next routing update. 12. Receive Sequence Numbers The sequence numbers that the gateway received in the last routing update from each of its neighbors. 13. Received Acknowledgement Vector A vector indicating whether or not each neighbor has acknowledged the sequence number in the most recent routing update sent. - 24 - 16. Events and Responses The following is a list of the events that occur at a gateway and the gateway's responses. The variables and tables referred to are listed above. This is a general guide for an implementation; see the sections above for the details of the various computations. 1. Connectivity to a network to which the gateway is attached changes. 1. Update the Minimum Distance Vector. 2. Recompute the Routing Updates. 3. Recompute the Routing Table. 4. If any routing update has changed, send the new routing updates to the neighbors. 2. Connectivity to a neighbor gateway changes. 1. Update the Neighbor Connectivity Vector. 2. Recompute the Minimum Distance Vector. 3. Recompute the Routing Updates. 4. Recompute the Routing Table. 5. If any routing update has changed, send the new routing updates to the neighbors. 3. A Routing Update Packet is received. 1. Compare the internet source address of the Routing Update Packet to the Neighbor Addresses. If the address is not on the list, add it to the list of Neighbor Addresses, increment the Number of Neighbors, and set the Receive Sequence Number for this neighbor to the sequence number in the Routing Update Packet. 2. Compare the Receive Sequence Number for this neighbor to the sequence number in the Routing Update Packet to determine whether or not to accept this packet. If the packet is rejected, send a Negative Acknowledgement Packet. If the packet is accepted, send an Acknowledgement Packet and proceed with the following steps. - 25 - 3. Compare the number of networks reported on in the Routing Update Packet to the Number of Networks. If the number of networks in the packet is greater than the Number of Networks, then replace Number of Networks with the number of networks in the packet. Expand the Distance Matrix to account for the new networks. 4. Copy the routing update received into the appropriate row of the Distance Matrix. 5. Recompute the Minimum Distance Vector. 6. Recompute the Routing Updates. 7. Recompute the Routing Table. 8. If any routing update has changed, send the new routing updates to the neighbors. 4. An Acknowledgement or Negative Acknowledgement Packet is received. 1. Compare the sequence number in the packet to the Send Sequence Number. If necessary, replace the Send Sequence Number, and retransmit the routing updates. If the Send Sequence Number is acknowledged, update the entry in the Received Acknowledgment Vector for the neighbor that sent the acknowledgement. 5. A data packet is received. 1. Forward the data packet using the information in the Routing Table entry for the packet's destination network. 2. If the destination is unreachable, send a Destination Unreachable Packet to the internet source of the data packet. 3. If the data packet is discarded because there are no buffers available in the gateway, then send a Source Quench Packet to the internet source of the data packet. 4. If the gateway to which the data packet is being forwarded and the data packet's internet source are on the same network, send a Redirect Packet to the internet source of the data packet. - 26 -